#include<iostream>
#include<vector>
#include<queue>
using namespace std;

class Node {
public:
	int val;
	Node* left;
	Node* right;
	Node* next;
	Node() : val(0), left(NULL), right(NULL), next(NULL) {}
	Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
	Node(int _val, Node* _left, Node* _right, Node* _next)
		: val(_val), left(_left), right(_right), next(_next) {}
};

class Solution {
public:
	Node* connect(Node* root) {
		if (!root)
			return NULL;
		queue<Node *> q;
		q.push(root);
		while (!q.empty()) {
			int count = q.size();
			Node *p,*last=NULL;
			for (int i = 1; i <= count; i++) {
				p = q.front();
				q.pop();
				if (p->left)
					q.push(p->left);
				if (p->right)
					q.push(p->right);
				if (i != 1)
					last->next = p;
				last = p;
			}
		}
		return root;
	}
};

void main() {
	Node root(1), l1(2), l2(3), l3(4), l4(5), l5(6), l6(7);
	root.left = &l1, root.right = &l2, l1.left = &l3, l1.right = &l4, l2.right = &l6;
	Solution s;
	s.connect(&root);
}